package algorithmicFoundation.homework.day3;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 随机队列
 *
 * @author 86155
 * @date 2025/08/09
 */
public class RandomizedQueue<Item> implements Iterable<Item> {

    /**
     * 装载数据
     */
    private Item[] items;

    /**
     * 指向最先添加的节点
     */
    private int head = 0;
    /**
     * 指向需要添加的尾部节点
     */
    private int tail = 0;

    private final int DEFAULT_CAPACITY = 10;

    // construct an empty randomized queue
    public RandomizedQueue(){
        //初始化
        items = (Item[]) new Object[DEFAULT_CAPACITY];
    }

    // is the randomized queue empty?
    public boolean isEmpty(){
        return tail - head == 0;
    }

    // return the number of items on the randomized queue
    public int size(){
        return tail - head;
    }

    // add the item
    public void enqueue(Item item){
        //校验
        vail(item);
        if (this.tail >= this.items.length) {
            //需要扩容
            resize(true);
        }
        this.items[tail++] = item;
    }
    private void vail(Item item) {
        if (item == null) {
            throw new IllegalArgumentException("item is null");
        }
    }
    private void vail() {
        if (isEmpty()) {
            throw new NoSuchElementException("is empty");
        }
    }

    // remove and return a random item
    public Item dequeue(){
        vail();

        //删除随机元素时，选择数组中的一个随机位置，
        int index = StdRandom.uniformInt(this.head,this.tail);
        // 将该位置的元素与数组末尾的元素交换，
        Item temp = this.items[index];
        this.items[index] = this.items[head];
        this.items[head] = temp;

        // 然后删除末尾元素
        // 移除头部元素（原随机元素）
        Item result = items[head];
        // 避免对象游离 jvm回收
        items[head] = null;
        head++;

        // 缩容条件：使用率<25% 且容量>默认值
        if (size() > 0 && size() == items.length / 4 && items.length > DEFAULT_CAPACITY) {
            resize(false);
        }

        return result;
    }
    /**
     * true:需要扩容
     * false: 收缩空间
     */
    private void resize(boolean isExpansion) {
        int len = this.items.length;
        int size = size();
        int newLen = isExpansion ?
                len << 1 :
                //放置收容过小
                Math.max(DEFAULT_CAPACITY, len >>> 1);
        //双倍扩容 //双倍扩容
        Item[] newArray = (Item[]) new Object[newLen];
        //复制数据 紧凑复制元素
        System.arraycopy(items,head,newArray,0,size);

        //覆盖
        this.items = newArray;
        this.head = 0;
        this.tail = size;
    }

    // return a random item (but do not remove it)
    public Item sample(){
        //校验并随机返回
        vail();
        int index = StdRandom.uniformInt(this.head,this.tail);
        return this.items[index];
    }

    // return an independent iterator over items in random order
    @Override
    public Iterator<Item> iterator() {
        return new RandomizedQueueIterator();
    }

    private class RandomizedQueueIterator implements Iterator<Item> {
        private final Item[] shuffledItems; // 独立数组
        private int current = 0;

        public RandomizedQueueIterator() {
            // 1. 复制当前元素
            shuffledItems = (Item[]) new Object[size()];
            for (int i = 0; i < shuffledItems.length; i++) {
                shuffledItems[i] = items[head + i];
            }

            // 2. Fisher-Yates 洗牌算法
            StdRandom.shuffle(shuffledItems);
        }

        @Override
        public boolean hasNext() {
            return current < shuffledItems.length;
        }

        @Override
        public Item next() {
            if (!hasNext()) {throw new NoSuchElementException();}
            return shuffledItems[current++];
        }
    }

    // unit testing (required)
    public static void main(String[] args){
        RandomizedQueue<Integer> que = new RandomizedQueue<>();
        que.enqueue(1);
        que.enqueue(3);
        que.enqueue(5);
        for (int a : que) {
            System.out.println(a);
        }
        System.out.println(que.size());
        System.out.println(que.sample());
        System.out.println(que.sample());
        System.out.println(que.sample());
        System.out.println(que.sample());
        System.out.println(que.dequeue());
        System.out.println(que.dequeue());
        System.out.println(que.size());
    }

}